package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 2. Add Two Numbers
 *
 * You are given two non-empty linked lists representing two non-negative integers.
 * The digits are stored in reverse order, and each of their nodes contains a single digit.
 * Add the two numbers and return the sum as a linked list.
 *
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * Example 1:
 *  Input: l1 = [2,4,3], l2 = [5,6,4]
 *  Output: [7,0,8]
 *  Explanation: 342 + 465 = 807.
 *
 * Example 2:
 *  Input: l1 = [0], l2 = [0]
 *  Output: [0]
 *
 * Example 3:
 *  Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 *  Output: [8,9,9,9,0,0,0,1]
 *
 * Constraints:
 *  The number of nodes in each linked list is in the range [1, 100].
 *  0 <= Node.val <= 9
 *  It is guaranteed that the list represents a number that does not have leading zeros.
 */
public class Num_0002 implements LeetCode {

    private interface Solution extends LinkedList {
        ListNode addTwoNumbers(ListNode l1, ListNode l2);

        default void assertExpected(int[] l1, int[] l2, int[] expected) {
            if (!assertEquals(addTwoNumbers(build(l1), build(l2)), build(expected))) {
                addTwoNumbers(build(l1), build(l2));
            }
        }
    }

    private static class MySolution implements Solution {

        private int getVal(ListNode node) {
            return node == null ? 0 : node.val;
        }

        private ListNode next(ListNode node) {
            return node == null ? null : node.next;
        }

        @Override
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 最优：相加后再生成 ListNode：时O(max{m,n}) 空O(1)
            /*
             * 两数相加（逆序排列位数）
             * [2,4,3] + [5,6,4] => [7,0,8]
             * : 342 + 465 = 807
             *
             * 相加后再生成 ListNode
             */
            ListNode result = null;
            ListNode prev = null;
            ListNode cur;
            int over = 0; // 是否进位
            while (l1 != null || l2 != null || over > 0) {
                int add = getVal(l1) + getVal(l2) + over;
                if (add > 9) {
                    cur = new ListNode(add - 10);
                    over = 1;
                } else {
                    cur = new ListNode(add);
                    over = 0;
                }
                if (prev == null) {
                    result = cur;
                } else {
                    prev.next = cur;
                }
                prev = cur;
                l1 = next(l1);
                l2 = next(l2);
            }
            return result;
        }
    }

    private static class MyAnotherSolution implements Solution {

        private int getVal(ListNode node) {
            return node == null ? 0 : node.val;
        }

        private ListNode next(ListNode node) {
            return node == null ? null : node.next;
        }

        private boolean hasNext(ListNode node) {
            return node != null && node.next != null;
        }

        private int getNextVal(ListNode node) {
            return node != null && node.next != null ? node.next.val : 0;
        }

        @Override
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //[废弃] 时O(max{m,n}) 空O(1)
            /*
             * 两数相加（逆序排列位数）
             * [2,4,3] + [5,6,4] => [7,0,8]
             * : 342 + 465 = 807
             *
             * 相加前先生成 ListNode
             */
            ListNode result = null;
            ListNode prev = null;
            ListNode cur;
            while (l1 != null || l2 != null || hasNext(prev)) {
                int add = getVal(l1) + getVal(l2) + getNextVal(prev);
                if (add > 9) {
                    cur = new ListNode(add - 10, new ListNode(1));
                } else {
                    cur = new ListNode(add);
                }
                if (prev == null) {
                    result = cur;
                } else {
                    prev.next = cur;
                }
                prev = cur;
                l1 = next(l1);
                l2 = next(l2);
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{2,4,3}, new int[]{5,6,4}, new int[]{7,0,8});
        solution.assertExpected(new int[]{0}, new int[]{0}, new int[]{0});
        solution.assertExpected(new int[]{9,9,9,9,9,9,9}, new int[]{9,9,9,9}, new int[]{8,9,9,9,0,0,0,1});
    }
}
